package com.currentbp.Interesting.likou.complete;

import org.junit.Test;

/**
 * @author baopan
 * @createTime 2024/3/20 23:00
 */
public class T1395numTeams {
    /*
n 名士兵站成一排。每个士兵都有一个 独一无二 的评分 rating 。
每 3 个士兵可以组成一个作战单位，分组规则如下：
从队伍中选出下标分别为 i、j、k 的 3 名士兵，他们的评分分别为 rating[i]、rating[j]、rating[k]
作战单位需满足： rating[i] < rating[j] < rating[k] 或者 rating[i] > rating[j] > rating[k] ，其中  0 <= i < j < k < n
请你返回按上述条件可以组建的作战单位数量。每个士兵都可以是多个作战单位的一部分。
示例 1：
输入：rating = [2,5,3,4,1]
输出：3
解释：我们可以组建三个作战单位 (2,3,4)、(5,4,1)、(5,3,1) 。
示例 2：
输入：rating = [2,1,3]
输出：0
解释：根据题目条件，我们无法组建作战单位。
示例 3：
输入：rating = [1,2,3,4]
输出：4
     */
    /*
    解题思路1：
    1、暴力拆解：
    1.1、先从左到右，三个游标，依次向右滑动，并判断是否是符合规则
    解题思路2：
    2.1、由于一共就三个游标，
    2.2、可以把中间的游标固定，
    2.2.1、判断出左边比中间小的，右边比中间大的
    2.2.2、判断出左边比中间大的，右边比中间小的
    2.2.3、累加起来就是中间游标固定后的符合规则数量
    2.3、以此类推固定住中间的数，判断其他的情况
     */
    @Test
    public void t1() {
        System.out.println(numTeams2(new int[]{2, 5, 3, 4, 1}));
        System.out.println(numTeams2(new int[]{2, 1, 3}));
        System.out.println(numTeams2(new int[]{1, 2, 3, 4}));
    }

    public int numTeams2(int[] rating) {
        if (null == rating || rating.length < 3) {
            return 0;
        }

        int result = 0;
        for (int middle = 1; middle < rating.length - 1; middle++) {
            result += doSumMiddle(rating, middle);
        }

        return result;
    }

    private int doSumMiddle(int[] rating, int middle) {
        int[] ints = fixMiddleNums(rating, middle);
        int result = 0;

        result = result + ints[0] * ints[1];
        result = result + ints[2] * ints[3];

        return result;
    }

    private int[] fixMiddleNums(int[] rating, int middle) {
        int[] result = new int[4];

        int left_min = 0;
        int left_max = 0;
        for (int i = 0; i < middle; i++) {
            if (rating[i] < rating[middle]) {
                left_min++;
            }
            if (rating[i] > rating[middle]) {
                left_max++;
            }
        }

        int right_min = 0;
        int right_max = 0;
        for (int i = middle + 1; i < rating.length; i++) {
            if (rating[i] < rating[middle]) {
                right_min++;
            }
            if (rating[i] > rating[middle]) {
                right_max++;
            }
        }
        result[0] = left_min;
        result[1] = right_max;
        result[2] = left_max;
        result[3] = right_min;
        return result;
    }

    //超时，在预期范围内
    public int numTeams(int[] rating) {
        if (null == rating || rating.length < 3) {
            return 0;
        }
        int result = 0;
        for (int left = 0; left < rating.length - 2; left++) {
            for (int middle = left + 1; middle < rating.length - 1; middle++) {
                for (int right = middle + 1; right < rating.length; right++) {
                    if (isGood(rating, left, middle, right)) {
                        result++;
                    }
                }
            }
        }

        return result;
    }

    private boolean isGood(int[] rating, int left, int middle, int right) {
        if (rating[left] < rating[middle] && rating[middle] < rating[right]) {
            return true;
        }
        if (rating[left] > rating[middle] && rating[middle] > rating[right]) {
            return true;
        }
        return false;
    }
}
